/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/open-the-lock
   @Language: C++
   @Datetime: 19-04-09 10:13
   */

class Solution {
public:
	/**
	 * @param deadends: the list of deadends
	 * @param target: the value of the wheels that will unlock the lock
	 * @return: the minimum total number of turns 
	 */
	int openLock(vector<string> &deadends, string &target) {
		// Write your code here
		unordered_set<string> deadlock(deadends.begin(),deadends.end()), visit{{"0000"}};
		if(deadlock.count("0000") || deadlock.count(target)) return -1;
		if(target.compare("0000")==0) return 0;
		int step=0;
		for(queue<string> q{{"0000"}}; q.size();){
			++step;
			for(int n=q.size(); n--; q.pop()){
				const string &str=q.front();
				for(int i=0; i<str.length(); ++i){
					for(int j=-1; j<2; j+=2){
						string s=str;
						s[i]=(str[i]-'0'+10+j)%10+'0';
						if(target.compare(s)==0) return step;
						if(deadlock.count(s)<1 && visit.count(s)<1){
							q.push(s);
							visit.insert(s);
						}
					}
				}
			}
		}
		return -1;
	}
};
